package xin.yangshuai.leetcode01.question16;

//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//
//返回这三个数的和。
//
//假定每组输入只存在恰好一个解。
//
//
//
//示例 1：
//
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
//
//示例 2：
//
//输入：nums = [0,0,0], target = 1
//输出：0
//
//
//
//提示：
//
//    3 <= nums.length <= 1000
//    -1000 <= nums[i] <= 1000
//    -104 <= target <= 104

public class Question16 {

    public static void main(String[] args) {
        Question16.Solution solution = new Question16.Solution();

        int[] nums = {13, 252, -87, -431, -148, 387, -290, 572, -311, -721, 222, 673, 538, 919, 483, -128, -518, 7, -36, -840, 233, -184, -541, 522, -162, 127, -935, -397, 761, 903, -217, 543, 906, -503, -826, -342, 599, -726, 960, -235, 436, -91, -511, -793, -658, -143, -524, -609, -728, -734, 273, -19, -10, 630, -294, -453, 149, -581, -405, 984, 154, -968, 623, -631, 384, -825, 308, 779, -7, 617, 221, 394, 151, -282, 472, 332, -5, -509, 611, -116, 113, 672, -497, -182, 307, -592, 925, 766, -62, 237, -8, 789, 318, -314, -792, -632, -781, 375, 939, -304, -149, 544, -742, 663, 484, 802, 616, 501, -269, -458, -763, -950, -390, -816, 683, -219, 381, 478, -129, 602, -931, 128, 502, 508, -565, -243, -695, -943, -987, -692, 346, -13, -225, -740, -441, -112, 658, 855, -531, 542, 839, 795, -664, 404, -844, -164, -709, 167, 953, -941, -848, 211, -75, 792, -208, 569, -647, -714, -76, -603, -852, -665, -897, -627, 123, -177, -35, -519, -241, -711, -74, 420, -2, -101, 715, 708, 256, -307, 466, -602, -636, 990, 857, 70, 590, -4, 610, -151, 196, -981, 385, -689, -617, 827, 360, -959, -289, 620, 933, -522, 597, -667, -882, 524, 181, -854, 275, -600, 453, -942, 134};
        int i = solution.threeSumClosest(nums, -2805);
        System.out.println(i);
    }

    static class Solution {
        public int threeSumClosest(int[] nums, int target) {

            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int a = nums[i];
                    int b = nums[j];
                    if (a > b) {
                        nums[i] = b;
                        nums[j] = a;
                    }
                }
            }

            int sum = nums[0] + nums[1] + nums[2];
            int diff;
            int tempSum;
            int tempDiff;
            if (sum > target) {
                return sum;
            } else {
                diff = target - sum;
            }


            for (int i = 0; i < nums.length - 2; i++) {
                tempSum = nums[i];

                // 如果tempSum大于target，并且tempSum-target大于diff，并且当前大于等于0，加上后续一定大于等于当前的tempSum，不用再循环了，break
                if (tempSum > target) {
                    tempDiff = tempSum - target;
                    if (tempDiff > diff && tempSum >= 0) {
                        break;
                    }
                }

                for (int j = i + 1; j < nums.length - 1; j++) {
                    tempSum = nums[i] + nums[j];

                    // 如果tempSum大于target，并且tempSum-target大于diff，并且当前大于等于0，加上后续一定大于等于当前的tempSum，不用再循环了，break
                    if (tempSum > target) {
                        tempDiff = tempSum - target;
                        if (tempDiff > diff && tempSum >= 0) {
                            break;
                        }
                    }

                    for (int k = j + 1; k < nums.length; k++) {

//                        // 如果nums[i] + nums[j]小于target，nums[k]可从最大的小于0的数开始
//                        if (nums[i] + nums[j] < target) {
//
//                            if (k < nums.length - 1 && nums[k + 1] < 0) {
//                                continue;
//                            }
//                        }

                        tempSum = nums[i] + nums[j] + nums[k];

                        if (tempSum < target) {
                            // 如果tempSum小于target，判断target-tempSum与diff的大小
                            tempDiff = target - tempSum;
                            if (tempDiff < diff) {
                                diff = tempDiff;
                                sum = tempSum;
                            }
                            // 继续下次循环
                        } else if (tempSum > target) {
                            // 如果tempSum大于target，判断tempSum-target与diff的大小
                            tempDiff = tempSum - target;
                            if (tempDiff < diff) {
                                diff = tempDiff;
                                sum = tempSum;
                            }
                            // 如果当前大于等于0，后续一定比当前的tempSum大，不用再循环了，break
                            if (tempSum >= 0) {
                                break;
                            }
                        } else {
                            return tempSum;
                        }
                    }
                }
            }
            return sum;
        }
    }
}
